//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package 力扣.题库.枚举右_维护左;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class demo_2845 {
    public demo_2845() {
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        Collections.addAll(list, new Integer[]{11, 12, 21, 31});
        System.out.println(countInterestingSubarrays(list, 10, 1));
    }

    public static long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        int n = nums.size();
        int[] sum = new int[n + 1];

        for(int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + ((Integer)nums.get(i) % modulo == k ? 1 : 0);
        }

        int[] cnt = new int[Math.min(n + 1, modulo)];
        long ans = 0L;

        for(int s : sum) {
            if (s >= k) {
                ans += (long)cnt[(s - k) % modulo];
            }

            ++cnt[s % modulo];
        }

        return ans;
    }
}
